It is very common to add indexes to data to rapidly search a large amount of data for a small amount of data. As the target for which the searching process is frequently performed, databases are used. Of the databases, a relational database that manages data in a tabular form is one of the most widely used databases. A table is formed by rows and columns, and for example, one row contains data concerning one transaction. The row is formed by plural columns, and for example, a certain column contains date data, while another column contains a sales figure.
In this case, the total amount of sales at a specific date can be obtained, for example, through full scan or index scan. In the full scan, examination for all the rows is made as to whether the dates are matched or not, and the sales figures in the matched rows are added up. In the index scan, the rows having the date matched with each other are specified using indexes, whereby the total of the sales figures can be obtained from the specified rows. This index scan is efficient when the number of rows having the date matched is sufficiently small as compared with the number of all the rows.
A B-tree is known as a data structure that accommodates the indexes. For example, Non-patent Document 1 describes algorithms including searching with the B-tree, inserting of data into the B-tree, and deleting data in the B-tree. Non-patent Document 2 makes an explanation of the B-tree in ORACLE (trademark) in relation to the widely used relational database.
With the B-tree index, it is possible to search for the data with the calculation amount in proportion to “log n,” where n is the number of rows. Note that the amount of calculation in the full scan is in proportion to the n.
Further, Patent Document 1 proposes an index management method of preparing indexes with plural tree structures and storing the key value in any one of the tree structures to reduce lock contention occurring when plural accesses occur to the same key value. With this method, the number of keys in the index is equalized, and the number of accesses is counted for each of the indexes, whereby it is possible to equalize the access load for each of the indexes.
Patent Document 2 proposes a method of managing a database, in which the number of lock contentions in the B-tree index is counted, and the B-tree is divided in the case where the large number of lock contentions occurs.
Patent Document 3 proposes a method of processing a record addition, in which, in the case where records are added to a balance tree such as the B-tree, the block is extended so as to have a size that can be read/written through one input/output process without the block being divided. Note that, with this method, the block division is performed after the block is extended to the maximum extendable size.
Patent Document 4 proposes a split control system in a data processing system managing data with a storage structure employing a non-dense B-tree cluster structure. With this method, the block division at the time of overflow is not immediately performed, and the target record is written into the overflow area, thereby reducing the overhead of the block division process.
Further, Non-patent Document 3 proposes a reverse-key index method designed so as to remove the hot spot in indexes in the inserting application. For example, in the case where the B-tree index is added to the column indicating the time when data is inserted, the write accesses are focused on the leaf block furthest to the right in the index (leaf block having the maximum value) and the branch block located above the leaf block. In order to avoid such a situation, which is called a right-growing index, the reverse-key index method is configured by reversing the key value in the index. More specifically, in the general index, a key value (102) and a key value (103) are inserted into the same block. However, in the reverse-key index, these key values are treated as the reversed values (201) and (301), and thus, are inserted into different blocks.